package math;

/**
 * 给定一个数组arr，该数组无序，但每个值均为正数，再给定一个正数k。求 arr 的所有子数组中所有元素相加和为k 的最长子数组长度。
 * 例如，arr=[1,2,1,1,1]，k=3。
 * 累加和为3的最长子数组为[1,1,1]，所以结果返回3。要求:时间复杂度0(N)，额外空间复杂度0(1)
 *
 * @author Liaorun
 */
public class LongestSumSubArrayLengthInPositiveArray {

    public static int getMaxLength(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k <= 0) {
            return 0;
        }

        // 如果 left == right + 1表示窗口不在有数
        int left = 0;
        int right = 0;
        int sum = arr[0];
        int len = 0;
        while (right < arr.length) {
            if (sum == k) {
                // 检查是否能更新最大长度
                len = Math.max(len, right - left + 1);
                // 左指针向右走一格，减去出去的数
                sum -= arr[left++];
            } else if (sum < k) {
                // 区间的数的和达不到目标
                // 右指针右移
                right++;
                if (right == arr.length) {
                    // 数组越界跳出
                    break;
                }
                // 加上进来的数
                sum += arr[right];
            } else {
                // sum > k,左指针向右走一格，减去出去的数
                sum -= arr[left++];
            }
        }

        return len;
    }
}
